'''
Created on Jun 22, 2011

@author: rreyes
'''


from yacf.Frontend.Common.IRNode import IRNodeVisitor
from yacf.Frontend.C99 import c99_ast
from yacf.Backends.Common.Visitors.GenericVisitors import FilterVisitor, AnyIDVisitor
from yacf.Frontend.SymbolTable import IdentifierNotFound

class DNode(object):
    def __init__(self, symbol):
        """ """
        self._name = symbol.name
        self._symbol = symbol
        self._pred = set()
        self._succ = set()
        self._isRead = False
        self._isWrite = False
        pass

    @property
    def symbol(self):
        return self._symbol

    @symbol.setter
    def symbol(self, symbol):
        self._symbol = symbol

    @property
    def name(self):
        return self._name

    @property
    def isRead(self):
        return self._isRead

    def markRead(self):
        self._isRead = True

    @property
    def isWrite(self):
        return self._isWrite

    def markWrite(self):
        self._isWrite = True


    @property
    def pred(self):
        return self._pred

    @property
    def succ(self):
        return self._succ

    def addPred(self, pred):
        self._pred.add(pred)


    def addSucc(self, succ):
        self._succ.add(succ)


    def hasPred(self, name):
         if name in self._pred:
            return True
         return False

    def hasSucc(self, name):
         if name in self._succ:
            return True
         return False

class DGraph({}.__class__):
    def checkDependency(self, from_name, to_name):
        # Quick return if possible
        if self[from_name.symbol].hasPred(to_name.symbol):
                return True
        # Increase distance
        visited = from_name.pred.copy()
        revisited = set()
        while len(visited) > 0:
            actual = visited.pop()
            revisited.add(actual)
            if self[actual].hasPred(to_name.symbol):
                return True
            visited.update(self[actual].pred.copy())
            visited.difference_update(revisited)
        return False


# FuncCall ignored for now
class DGraphBuilder(IRNodeVisitor):
    """ Returns an IdentifierType  """

    def __init__(self, depGraph, symbolTable):
        self._depGraph = depGraph
        self._read = False
        self._write = False
        self._prevRead = []
        self._prevWrite = []
        self._isSubscript = False
        self._visited = set()
        self._subscriptVisited = set()
        self._st = symbolTable
        

    def push(self):
        self._prevRead.append(self._read)
        self._prevWrite.append(self._write)

    def pop(self):
        self._read = self._prevRead.pop()
        self._write = self._prevWrite.pop()

    def visit_Compound(self, node):
        for elem in node.block_items:
            self._visited = set()
            self.visit(elem)



    def visit_Decl(self, node):
        """ Declared variables are successors of rvalue variables.
            Init variables are predecessors of lvalue variables.
            Declared variables are written. Used variables are read
        """
        self.push()
        self._read = False
        self._write = True

        #self.visit()
        dnode = None
        declnode = self._st.lookUpDecl(node)
        if self._depGraph.has_key(declnode):
            dnode = self._depGraph[declnode]
        else:
            dnode = DNode(declnode)
        if self._read:
            dnode.markRead()
        if self._write:
            dnode.markWrite()
        self._depGraph[declnode] = dnode
        
        lvalue = [declnode,]
        self._visited = set()

        self._read = True
        self._write = False
        if node.init:
            self.visit(node.init)
        self._read = False

        rvalue = self._visited

        # Update succ/pred in terms of rvalue/lvalue items
        for elem in rvalue:
            for l in lvalue:
# Therefore  lvalue are enabled by rvalues
                self._depGraph[elem].addSucc(l)
                self._depGraph[l].addPred(elem)

        self.pop()

    def visit_Assignment(self, node):
        """ lvalue variables are successors of rvalue variables.
            rvalue variables are predecessors of lvalue variables.
            lvalue variables are written. rvalue variables are read
        """
        self.push()

        self._read = True
        self._write = False
        self.visit(node.rvalue)
        rvalue = self._visited
        self._read = False

        if node.op == '=': # or node.op == '+=' or node.op == '-=' or node.op == '*=':
            self._read = False
        else:
            self._read = True

        self._write = True
        self.visit(node.lvalue)
        lvalue = self._visited
        self._visited = set()

        # Update succ/pred in terms of rvalue/lvalue items
        for r in rvalue:
            for l in lvalue:
#                    print " l : " + str(l) + " depends on r: " + str(r)
# Therefore  lvalue are enabled by rvalues
                    self._depGraph[l].addPred(r)
                    self._depGraph[r].addSucc(l)

        # Lvalue nodes have been visited also
        for l in lvalue:
            self._visited.add(l)
      
        self.pop()

    def visit_ExprList(self, node):
        """ All variables are read """
        if node.exprs:
            self.push()
            self._read = True
            for elem in node.exprs:
                self.visit(elem)
            self.pop()

    def visit_UnaryOp(self, node):
        """ Affected expression is read and written """
        self.push()
        self._read = True
        self._write = True
        self.visit(node.expr)
        self.pop()

    def visit_BinaryOp(self, node):
        """ Both right and left are read """
        self.push()
        self._read = True
        self.visit(node.left)
        self.visit(node.right)
        self.pop()

    def visit_FuncCall(self, node):
        """ Function Call ignored """
	if node.args:
		self.push()
		self._read = True
		self._write = True
		self.visit(node.args)
		self.pop()
        
    def visit_ArrayRef(self, node):
        """ Array Subscript do not generate dependencies """
        self._isSubscript = True
        self.push()
        self._write = False
        self.visit(node.subscript)
        self.pop()

        self._isSubscript = False
        
        prev = self._visited
        self._visited = set()
        self.visit(node.name)
        visited = self._visited
    
        visited.difference_update(self._subscriptVisited)
        prev.difference_update(self._subscriptVisited)
        
        
        for ar in visited:
            for sub in self._subscriptVisited:
#                print " l : " + str(ar) + " depends on r: " + str(sub)
# Therefore ar is enabled by sub
                self._depGraph[ar].addPred(sub)
                self._depGraph[sub].addSucc(ar)

        self._visited.update(prev)
        self._subscriptVisited.clear()

    def visit_ID(self, node):
        """ Identify var and update pred/succ """
        dnode = None
        try:
            if not isinstance(node.parent, c99_ast.StructRef):
                node = self._st.lookUp(node)
            else:
                node = self._st.lookUp(node.parent.name)
        except IdentifierNotFound:
            print " Error: Identifier " + str(node) + " not declared "
            import pdb
            pdb.set_trace()
            node = self._st.lookUp(node)
            raise IdentifierNotFound(node) 
        if self._depGraph.has_key(node):
            dnode = self._depGraph[node]
        else:
            dnode = DNode(node)
        if self._read:
            dnode.markRead()
        if self._write:
            dnode.markWrite()
        self._depGraph[node] = dnode
        
        self._visited.add(node)
        if self._isSubscript:
            self._subscriptVisited.add(node)

class ArrayIndexAnalysis(DGraphBuilder):
    pass

class BlockDepGraphBuilder(DGraphBuilder):

    def __init__(self, depGraph, symbolTable):
        """ Builds a dependency graph between the stmts/subblocks of a given Compoud Statement (Block)."""
        self._blockDeps = []
        self._blockWrite = []
        self._blockRead = []
        self._visitedFirst = False
        self._visitedFirst_node = None
        super(BlockDepGraphBuilder, self).__init__(depGraph, symbolTable)

    def getBlockDeps(self):
        return self._blockDeps


    def getBlockWrite(self):
        return self._blockWrite


    def getBlockRead(self):
        return self._blockRead


    def setBlockDeps(self, value):
        self._blockDeps = value


    def setBlockWrite(self, value):
        self._blockWrite = value


    def setBlockRead(self, value):
        self._blockRead = value


    def delBlockDeps(self):
        del self._blockDeps


    def delBlockWrite(self):
        del self._blockWrite


    def delBlockRead(self):
        del self._blockRead


    def visit_Compound(self, node):
        if self._visitedFirst:
            super(BlockDepGraphBuilder,self).visit_Compound(node)
        else:
            self._visitedFirst = True
            self._visitedFirst_node = node
            count = 0
            for elem in node.block_items:
                # Reset dependency graph for each statement
                self._depGraph = {}
                self._visited = set()
#                print " S" + str(count) + ": ",
                self.visit(elem)
#                print " Visited nodes (outside): " + str([str(v) for v in self._visited]) 
#                print " depGraph nodes (outside): " + str([d.name + ":" + str(self._depGraph[d].isWrite) for d in self._depGraph]) 
                # Update information for block
                self._blockDeps.append(self._visited)
                self._blockWrite.append([var for var in self._visited if self._depGraph[var].isWrite]) 
                self._blockRead.append([var for var in self._visited if self._depGraph[var].isRead])
                count = count + 1
#                print "Read vars: " + str([str([var.name for var in stmt])  for stmt in self._blockRead])
#                print "Write vars: " + str([str([var.name for var in stmt])  for stmt in self._blockWrite])
            

    def computeDependencyMatrix(self,):
        """ Extract the stmt dependency matrix from the analyzed block.

            Returns two lists: The Statement dependency matrix and 
                                    the variable requisites  matrix

        """
        if not self._visitedFirst_node:
            raise NotImplemented
        # Statements that must come first of the i-th one
        predStmt = []
        # Variables whose value must be known prior executing 
        # the i-th statement
        requiredVars = []
        # List of statements to analyze (usually, the block_items 
        #                               attribute of the compound)
        block = self._visitedFirst_node.block_items
        # Number of stmts inside the block
        numStmts = len(self._visitedFirst_node.block_items)
        # Init lists (one element per statement inside block_items)
        for i in range(0,numStmts):
            predStmt.append(set())
            requiredVars.append(set())
        
        # Identify statement dependencies
        i = 0
        for i in range(0,numStmts):
            for j in range(i + 1,numStmts):
                for wvar in self.blockWrite[i]:
                    # RAW dependency
                    # If a var written in Si is read in Sj, 
                    #   then Si must finish before Sj 
                    if wvar in self.blockRead[j]:
                        predStmt[j].add(i)
                        requiredVars[j].add(wvar)
                    # Finish of RAW dependency
                    if wvar in self.blockWrite[j]:
                        # After this point, the update of Si
                        # is not relevant for Sj+1..N
                        break

        return [predStmt, requiredVars,]
   
    blockDeps = property(getBlockDeps, setBlockDeps, delBlockDeps, "Block vars")
    blockWrite = property(getBlockWrite, setBlockWrite, delBlockWrite, "Vars written at block")
    blockRead = property(getBlockRead, setBlockRead, delBlockRead, "Vars read at block")


